
// import haxe.ds.Array;
// import oimo.m.Vec3;
// import oimo.m.M;
// import oimo.collision.broadphase.bvh.*;

import { BvhNode } from "./BvhNode";
import { Vec3 } from "../../../common/Vec3";
import { M } from "../../../common/M";
import { BvhInsertionStrategy } from "./BvhInsertionStrategy";

/**
 * numberernal class.
 *
 * BVH strategy for BVH tree
 */


export class BvhStrategy {
	_insertionStrategy: number;
	_balancingEnabled: boolean;

	constructor() {
		this._insertionStrategy = BvhInsertionStrategy.SIMPLE;
		this._balancingEnabled = false;
	}

	// --- internal ---

	/**
	 * Returns the next step of leaf insertion.
	 * `0` or `1` to descend to corresponding child of current node.
	 * `-1` to stop descending and make common parent with current node.
	 */
	public _decideInsertion(currentNode: BvhNode, leaf: BvhNode): number {
		switch (this._insertionStrategy) {
			case BvhInsertionStrategy.SIMPLE:
				return this.decideInsertionSimple(currentNode, leaf);
			case BvhInsertionStrategy.MINIMIZE_SURFACE_AREA:
				return this.decideInsertionMinimumSurfaceArea(currentNode, leaf);
			default:
				console.error("invalid BVH insertion strategy: " + this._insertionStrategy);
				return -1;
		}
	}

	/**
	 * Sorts `leaves` and returns the split index `k` of the half-open interval [`from`, `until`).
	 * Leaves are separated into [`from`, `k`) and [`k`, `until`).
	 */
	public _splitLeaves(leaves: Array<BvhNode>, from: number, until: number): number {
		return this.splitLeavesMean(leaves, from, until);
	}

	// --- ---


	private decideInsertionSimple(currentNode: BvhNode, leaf: BvhNode): number {
		var center: Vec3 = new Vec3();
		M.vec3_add(center, leaf._aabbMin, leaf._aabbMax);

		var c1: BvhNode = currentNode._children[0];
		var c2: BvhNode = currentNode._children[1];
		var diff1: Vec3 = new Vec3();
		var diff2: Vec3 = new Vec3();
		M.vec3_add(diff1, c1._aabbMin, c1._aabbMax);
		M.vec3_add(diff2, c2._aabbMin, c2._aabbMax);
		M.vec3_sub(diff1, diff1, center);
		M.vec3_sub(diff2, diff2, center);
		var dist1: number = M.vec3_dot(diff1, diff1);
		var dist2: number = M.vec3_dot(diff2, diff2);

		return dist1 < dist2 ? 0 : 1;
	}


	private decideInsertionMinimumSurfaceArea(currentNode: BvhNode, leaf: BvhNode): number {
		var c1: BvhNode = currentNode._children[0];
		var c2: BvhNode = currentNode._children[1];

		var oldArea: number = M.aabb_surfaceArea(currentNode._aabbMin, currentNode._aabbMax);

		var combinedMin: Vec3 = new Vec3();
		var combinedMax: Vec3 = new Vec3();
		M.aabb_combine(combinedMin, combinedMax, currentNode._aabbMin, currentNode._aabbMax, leaf._aabbMin, leaf._aabbMax);

		var newArea: number = M.aabb_surfaceArea(combinedMin, combinedMax);

		// cost of creating new pair with the node
		var creatingCost: number = newArea * 2;
		var incrementalCost: number = (newArea - oldArea) * 2;

		var descendingCost1: number = incrementalCost;
		M.aabb_combine(combinedMin, combinedMax, c1._aabbMin, c1._aabbMax, leaf._aabbMin, leaf._aabbMax);
		if (c1._height == 0) {
			// leaf cost = area(combined aabb)
			descendingCost1 += M.aabb_surfaceArea(combinedMin, combinedMax);
		} else {
			// node cost = area(combined aabb) - area(old aabb)
			descendingCost1 += M.aabb_surfaceArea(combinedMin, combinedMax) - M.aabb_surfaceArea(c1._aabbMin, c1._aabbMax);
		}

		var descendingCost2: number = incrementalCost;
		M.aabb_combine(combinedMin, combinedMax, c2._aabbMin, c2._aabbMax, leaf._aabbMin, leaf._aabbMax);
		if (c2._height == 0) {
			// leaf cost = area(combined aabb)
			descendingCost2 += M.aabb_surfaceArea(combinedMin, combinedMax);
		} else {
			// node cost = area(combined aabb) - area(old aabb)
			descendingCost2 += M.aabb_surfaceArea(combinedMin, combinedMax) - M.aabb_surfaceArea(c2._aabbMin, c2._aabbMax);
		}

		return M.compare3min(creatingCost, descendingCost1, descendingCost2);
	}


	private splitLeavesMean(leaves: Array<BvhNode>, from: number, until: number): number {
		var invN: number = 1.0 / (until - from);

		// mean := sum(min + max) / n
		var centerMean: Vec3 = new Vec3();
		M.vec3_zero(centerMean);
		for (let i = from; i < until; ++i) {
			var leaf: BvhNode = leaves[i];
			M.vec3_add(leaf._tmp, leaf._aabbMax, leaf._aabbMin);
			M.vec3_add(centerMean, centerMean, leaf._tmp);
		}
		M.vec3_scale(centerMean, centerMean, invN);

		var variance: Vec3 = new Vec3();
		M.vec3_zero(variance);
		for (let i = from; i < until; ++i) {
			var leaf: BvhNode = leaves[i];
			var diff: Vec3 = new Vec3();
			M.vec3_sub(diff, leaf._tmp, centerMean);
			M.vec3_compWiseMul(diff, diff, diff);
			M.vec3_add(variance, variance, diff);
		}

		// sort and split
		var varX: number = M.vec3_get(variance, 0);
		var varY: number = M.vec3_get(variance, 1);
		var varZ: number = M.vec3_get(variance, 2);
		var l: number = from;
		var r: number = until - 1;
		switch (M.compare3max(varX, varY, varZ)) {
			case -1:
				{
					var mean: number = M.vec3_get(centerMean, 0);
					while (true) {
						while (true) {
							var leaf: BvhNode = leaves[l];
							if (M.vec3_get(leaf._tmp, 0) <= mean) break;
							l++;
						}
						while (true) {
							var leaf: BvhNode = leaves[r];
							if (M.vec3_get(leaf._tmp, 0) >= mean) break;
							r--;
						}
						if (l >= r) break;
						var tmp: BvhNode = leaves[l];
						leaves[l] = leaves[r];
						leaves[r] = tmp;
						l++;
						r--;
					}
				}
				break;
			case 0:
				{
					var mean: number = M.vec3_get(centerMean, 1);
					while (true) {
						while (true) {
							var leaf: BvhNode = leaves[l];
							if (M.vec3_get(leaf._tmp, 1) <= mean) break;
							l++;
						}
						while (true) {
							var leaf: BvhNode = leaves[r];
							if (M.vec3_get(leaf._tmp, 1) >= mean) break;
							r--;
						}
						if (l >= r) break;
						var tmp: BvhNode = leaves[l];
						leaves[l] = leaves[r];
						leaves[r] = tmp;
						l++;
						r--;
					}
				}
				break;
			case 1:
				{
					var mean: number = M.vec3_get(centerMean, 2);
					while (true) {
						while (true) {
							var leaf: BvhNode = leaves[l];
							if (M.vec3_get(leaf._tmp, 2) <= mean) break;
							l++;
						}
						while (true) {
							var leaf: BvhNode = leaves[r];
							if (M.vec3_get(leaf._tmp, 2) >= mean) break;
							r--;
						}
						if (l >= r) break;
						var tmp: BvhNode = leaves[l];
						leaves[l] = leaves[r];
						leaves[r] = tmp;
						l++;
						r--;
					}
				}
				break;
		}
		return l;
	}

}
